package 单调栈;

/**
 * @PackageName: 单调栈
 * @ClassName: LeetCode1249
 * @Author: chen jinxu
 * @Date: 2022/8/8 22:59
 * @Description: //
 * 给你一个由 '('、')' 和小写字母组成的字符串 s。
 *
 * 你需要从字符串中删除最少数目的 '(' 或者 ')'（可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
 *
 * 请返回任意一个合法字符串。
 *
 * 有效「括号字符串」应当符合以下任意一条要求：
 *
 * 空字符串或只包含小写字母的字符串
 * 可以被写作AB（A连接B）的字符串，其中A和B都是有效「括号字符串」
 * 可以被写作(A)的字符串，其中A是一个有效的「括号字符串」。
 *
 * 输入：s = "lee(t(c)o)de)"
 * 输出："lee(t(c)o)de"
 * 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案
 * 输入：s = "a)b(c)d"
 * 输出："ab(c)d"
 * 输入：s = "))(("
 * 输出：""
 * 解释：空字符串也是有效的
 */
public class LeetCode1249 {
    public static void main(String[] args) {
        System.out.println(minRemoveToMakeValid("lee(t(c)o)de)"));
        System.out.println(minRemoveToMakeValid("a)b(c)d"));
        System.out.println(minRemoveToMakeValid("))(("));
    }
    public static String minRemoveToMakeValid(String s) {
        //1 删除所有多余的 ）
        StringBuilder sb = new StringBuilder();
        int openLeft = 0;
        int balence = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                openLeft++;
                balence++;
            } else if (c == ')') {
                if (balence == 0) {
                    continue;
                }
                balence--;
            }
            sb.append(c);
        }
        //2 删除多余的( ,越靠近 左边越能和 ） 匹配，因此先匹配够后，再删除
        StringBuilder result = new StringBuilder();
        int openToKeep = openLeft - balence;
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (c == '(') {
                openToKeep--;
                if (openToKeep < 0) {
                    continue;
                }
            }
            result.append(c);
        }
        return result.toString();
    }
}
